package com.leetcodehot.problems;

import java.util.ArrayDeque;
import java.util.Deque;

public class problems1499 {
    /**
     * 满足不等式 yi + yj + |xi - xj|
     * 其中 |xi - xj| <= k 且 1 <= i < j <= points.length
     * 转化为 (xj + yj) + yi - xi
     */

    /**
     * 本题关键在于抽象出来(xj + yj) + yi - xi，然后对于后续的每一个点，xj+yj的部分没有任何关系，只需比较前面的y-x部分
     * 所以构建关于y-x的降序队列。并且以{x,y-x}来构建，方便弹出点。
     */
    public int findMaxValueOfEquation(int[][] points, int k) {
        int n = points.length;
        //存储 xj, yj-xj 维护一个 yj-xj的降序队列
        Deque<int[]> q = new ArrayDeque<>();

        int res = Integer.MIN_VALUE;
        for (int j = 0; j < n; j++) {
            int x = points[j][0];
            int y = points[j][1];
            //队首超出范围
            while (!q.isEmpty() && q.getFirst()[0] < x - k) {
                q.removeFirst();
            }
            if (!q.isEmpty()) {
                res = Math.max(res, x + y + q.getFirst()[1]);
            }
            while(!q.isEmpty() && q.getLast()[1] <= y-x) {
                q.removeLast();
            }
            q.addLast(new int[]{x, y - x});
        }
        return res;
    }
}
